An LDPC (Low Density Parity Check) code has a high error correction capability and is recently beginning to be employed in a transmission method including satellite digital broadcasting such as DVB (Digital Video Broadcasting)-S.2 conducted in Europe (for example, see Non-Patent Document 1). Further, employing the LDPC code in next generation terrestrial digital broadcasting is under consideration.
Recent studies have revealed that the LDPC code shows performance close to the Shannon limit as a code length increases, similarly to a turbo code or the like. Further, since the LDPC code has a property that a minimum distance is in proportion to a code length, there are advantageous, as features thereof, in that a block error probability characteristic is good, and a so-called error floor phenomenon observed in a decoding characteristic of a turbo code or the like hardly occurs.
The LDPC code will be concretely described below. The LDPC code is a linear code, and need not necessarily be binary, but the LDPC will be here described to be binary.
The most distinctive feature of the LDPC code is that a parity check matrix defining an LDPC code is sparse. Here, the sparse matrix is a matrix in which the number of elements “1s” of a matrix is very small (a matrix in which most of elements are “0”).
FIG. 1 illustrates an example of a parity check matrix H of an LDPC code.
In the parity check matrix H of FIG. 1, a weight (a column weight) (the number of “1s”) of each column is “3,” and a weight (row weight) of each row is “6.”
In encoding (LDPC coding) by an LDPC code, a code word (an LDPC code) is generated, for example, by generating a generation matrix G based on the parity check matrix H and multiplying a binary information bit by the generation matrix G.
Specifically, an encoding device performing LDPC coding first calculates the generation matrix G in which a formula GHT=0 is established with a transposed matrix HT of the parity check matrix H. Here, when the generation matrix G is a K×N matrix, the encoding device multiplies the generation matrix G by a bit string (a vector u) of information bits including K bits, and generates a code word c (=uG) including N bits. The code word (the LDPC code) generated by the encoding device is received at a reception side through a predetermined communication path.
The LDPC code can be decoded by a message passing algorithm that has been proposed as probabilistic decoding by Gallager and is based on belief propagation on the so-called tanner graph including a variable node (which is also called a message node) and a check node. Here, the variable node and the check node are hereinafter appropriately referred to simply as a node.
FIG. 2 illustrates an LDPC code decoding process.
Hereinafter, a real number value (reception LLR) in which a “0” likelihood of a value of an i-th code bit of an LDPC code (one code word) received at a reception side is represented by a log likelihood ratio is also appropriately referred to as a reception value u0i. Further, a message output from a check node is represented by uj, and a message output from a variable node is represented by vi.
First of all, in decoding of an LDPC code, as illustrated in FIG. 2, in step S11, an LDPC code is received, a message (check node message) uj is initialized to “0,” a variable k having an integer as a counter of a repeating process is initialized to “0,” and the process proceeds to step S12. In step S12, as a calculation (variable node calculation) represented by Formula (1) is performed based on the reception value u0i obtained when the LDPC code is received, a message (variable node message) vi is obtained, and as a calculation (check node calculation) represented by Formula (2) is performed based on the message vi, a message uj is obtained.
                    [                  Mathematical          ⁢                                          ⁢          Formula          ⁢                                                            ⁢                                                          ⁢          1                ]                                                                      v          i                =                              u                          0              ⁢              i                                +                                    ∑                              i                =                1                                            d                                  v                  -                  1                                                      ⁢                                                  ⁢                          u              j                                                          (        1        )                                [                  Mathematical          ⁢                                          ⁢          Formula          ⁢                                                            ⁢                                                          ⁢          2                ]                                                                      tanh          ⁡                      (                                          u                j                            2                        )                          =                              ∏                          i              =              1                                                      d                c                            -              1                                ⁢                                          ⁢                      tanh            ⁡                          (                                                v                  i                                2                            )                                                          (        2        )            
Here, in Formulas (1) and (2), dv and dc are parameters, which are arbitrarily selectable, representing the number of “1s” of the parity check matrix H in the longitudinal direction (column) and the lateral direction (row), and for example, in case of a (3, 6) code, dv is 3, and dc is 6.
In the variable node calculation of Formula (1) and the check node calculation of Formula (2), since a message input from an edge (a line connecting a variable node with a check node) from which a message is desired to be output is not a calculation target, a calculation range is 1 to dv−1 or 1 to dc−1. Further, actually, the check node calculation of Formula (2) is perform by generating a table of a function R (v1, v2) represented by Formula (3) defined by one output to two inputs v1 and v2 in advance and using the table consecutively (recursively) as represented by Formula (4).[Mathematical Formula 3]x=2 tan h−1[tan h(v1/2)tan h(v2/2)]=R(v1,v2)  (3)[Mathematical Formula 4]uj=R(v1,R(v2,R(v3, . . . R(vdo−2,vdo−1))))  (4).
In step S12, the variable k increases by “1,” and the process proceeds to step S13. In step S13, it is determined whether or not the variable k is larger than a predetermined repeated decoding number C. When it is determined in step S13 that the variable k is not larger than C, the process returns to step S12, and the same process is repeated.
Further, when it is determined in step S13 that the variable k is larger than C, the process proceeds to step S14, and the message vi is obtained and output as a decoding result finally output as a calculation represented by Formula (5) is performed, and then the LDPC code decoding process ends.
                    [                  Mathematical          ⁢                                          ⁢          Formula          ⁢                                                            ⁢                                                          ⁢          5                ]                                                                      v          i                =                              u                          0              ⁢              i                                +                                    ∑                              j                =                1                                            d                y                                      ⁢                                                  ⁢                          u              j                                                          (        5        )            
Here, the calculation of Formula (5) is performed using the message uj from all edges connected to the variable node, unlike the variable node calculation of Formula (1).
FIG. 3 illustrates an example of the parity check matrix H of a (3, 6) LDPC code (a coding rate is 1/2, and a code length is 12).
In the parity check matrix H of FIG. 3, a weight of a column is 3, and a weigh of a row is 6, similarly to FIG. 1.
FIG. 4 illustrates a tanner graph of the parity check matrix H of FIG. 3.
Here, in FIG. 4, a check node is represented by plus “+,” a variable node is represented by equal “=.” The check node and the variable node correspond to a row and a column of the parity check matrix H, respectively. A connection line between the check node and the variable node is an edge, and corresponds to an element “1” of the parity check matrix.
In other words, in FIG. 4, when an element of a j-th row and an i-th column of the parity check matrix is “1,” an i-th variable node (a node of “=”) from the top is connected with a j-th check node (a node of “+”) from the top by an edge. The edge represents that a code bit corresponding to a variable node has a constraint condition on a check node.
In a sum product algorithm used as an LDPC code decoding method, the variable node calculation and the check node calculation are repeatedly performed.
FIG. 5 illustrates the variable node calculation performed at the variable node.
In the variable node, a message vi corresponding to an edge that is desired to be calculated is obtained by the variable node calculation of Formula (1) using messages u1 and u2 from the remaining edges connected to the variable node and the reception value u0i. The messages corresponding to the other edges are similarly obtained.
FIG. 6 illustrates the check node calculation performed at the check node.
Here, the check node calculation of Formula (2) may be rewritten to Formula (6) using a relation of a formula a×b=exp{ln(|a|)+ln(|b|)}×sign(a)×sign (b). Here, sign (x) is 1 when x≧0 and −1 when x<0.
                    [                  Mathematical          ⁢                                          ⁢          Formula          ⁢                                                            ⁢                                                          ⁢          6                ]                                                                                                                u                j                            =                            ⁢                              2                ⁢                                                      tanh                                          -                      1                                                        ⁡                                      (                                                                  ∏                                                  i                          =                          1                                                                                                      d                            c                                                    -                          1                                                                    ⁢                                                                                          ⁢                                              tanh                        ⁡                                                  (                                                                                    v                              i                                                        2                                                    )                                                                                      )                                                                                                                          =                            ⁢                              2                ⁢                                                      tanh                                          -                      1                                                        ⁡                                      [                                          exp                      ⁢                                                                        {                                                                                    ∑                                                              i                                =                                1                                                                                            d                                                                  c                                  -                                  1                                                                                                                      ⁢                                                                                                                  ⁢                                                          ln                              ⁡                                                              (                                                                                                                                        tanh                                    ⁡                                                                          (                                                                                                                        v                                          i                                                                                2                                                                            )                                                                                                                                                                        )                                                                                                              }                                                ⨯                                                                              ∏                                                          i                              =                              l                                                                                                                      d                                c                                                            -                              1                                                                                ⁢                                                                                                          ⁢                                                      sign                            ⁡                                                          (                                                              tanh                                ⁡                                                                  (                                                                                                            v                                      i                                                                        2                                                                    )                                                                                            )                                                                                                                                            ]                                                                                                                                          =                                ⁢                                  2                  ⁢                                                                                    tanh                                                  -                          1                                                                    ⁡                                              [                                                  exp                          ⁢                                                      {                                                          -                                                              (                                                                                                      ∑                                                                          i                                      =                                      1                                                                                                              d                                                                              c                                        -                                        1                                                                                                                                              ⁢                                                                                                                                          ⁢                                                                      -                                                                          ln                                      ⁡                                                                              (                                                                                  tanh                                          ⁡                                                                                      (                                                                                                                                                                                                                                            v                                                  i                                                                                                                                                                                            2                                                                                        )                                                                                                                          )                                                                                                                                                                            )                                                                                      }                                                                          ]                                                              ⨯                                                                  ∏                                                  i                          =                          1                                                                                                      d                            c                                                    -                          1                                                                    ⁢                                                                                          ⁢                                              sign                        (                                                  v                          i                                                )                                                                                                        ⁢                                                                                                      (        6        )            
In case of x≧0, when a function φ(x) is defined as a formula φ(x)=ln(tan h(x/2)), since a formula φ−1(x)=2 tan h−1(e−x) is established, Formula (6) may be changed to Formula (7).
                    [                  Mathematical          ⁢                                          ⁢          Formula          ⁢                                                            ⁢                                                          ⁢          7                ]                                                                      u          j                =                                            ϕ                              -                1                                      ⁡                          (                                                ∑                                      i                    =                    1                                                        d                                          c                      -                      1                                                                      ⁢                                                                  ⁢                                  ϕ                  ⁡                                      (                                                                                        v                        i                                                                                    )                                                              )                                ⨯                                    ∏                              i                =                l                                                              d                  c                                -                1                                      ⁢                          sign              ⁡                              (                                  v                  i                                )                                                                        (        7        )            
In the check node, the check node calculation of Formula (2) is performed according to Formula (7).
In other words, in the check node, a message uj corresponding to an edge that is desired to be calculated is obtained by the check node calculation of Formula (7) using messages v1, v2, v3, v4, and v5 from remaining edges connected to the check node as illustrated FIG. 6. The messages corresponding to the other edges are similarly obtained.
The function φ(x) of Formula (7) may be represented by a formula φ(x)=ln((ex+1)/(ex−1)), and is φ(x)=φ−1(x) when x>0. When the functions φ(x) and φ−1(x) are implemented as hardware, an implementation method using an LUT (Look Up Table) may be used, but both become the same LUT.